package A03_稀疏数组和队列.A31_稀疏数组;

/**
 *
 * @Author: KingWang
 * @Date: 2021/5/29
 * @Desc:
 **/
public class SparseArrayDemo {
    public static void main(String[] args) {
        SparseArrayDemo demo = new SparseArrayDemo();

        int[][] arrs = new int[10][12];
        arrs[1][1] = 3;
        arrs[2][3] = 10;
        arrs[5][8] = 33;
        arrs[0][8] = 2;

        //正常情况下棋盘如下：
        demo.print(arrs);

        System.out.println("--------------转化为稀疏矩阵的如下-----------------");

        //要将arrs转化为稀疏数组sparseArr
        int[][] sparseArr = demo.convertSparse(arrs);
        demo.print(sparseArr);

        System.out.println("--------------还原为普通数组如下-----------------");
        demo.print(demo.convertNormal(sparseArr));


    }

    //将普通数组转换为稀疏数组
    public int[][] convertSparse(int[][] arrs){
        int rows = arrs[0].length;
        int cols = arrs.length;
        int valCount = 0;
        for(int[] arr:arrs){
            for(int i:arr){
                if(0 != i){
                    valCount++;
                }
            }
        }
        int[][] sparseArrs = new int[valCount+1][3];
        sparseArrs[0][0] = cols;  //原始数组的行数
        sparseArrs[0][1] = rows;  //原始数组的列数
        sparseArrs[0][2] = valCount; //原始数组有值的个数

        int num = 0;
        for (int i = 0; i <cols ; i++) {
            for (int j = 0; j <rows ; j++) {
                if(0!=arrs[i][j]){
                    ++num;
                    sparseArrs[num][0] = i;
                    sparseArrs[num][1] = j;
                    sparseArrs[num][2] = arrs[i][j];
                }
            }
        }
        return sparseArrs;
    }

    //将稀疏数组还原为普通数组
    public int[][] convertNormal(int[][] sparseArrs){
        //计算数组初始化大小值
        int cols = sparseArrs[0][0];
        int rows = sparseArrs[0][1];
        int valCount = sparseArrs[0][2];

        //创建Normal数组
        int[][] normalArrs = new int[cols][rows];

        //遍历稀疏数组，取值后赋值到Normal数组
        for (int i = 1; i <(valCount+1) ; i++) {
            int normalCol = sparseArrs[i][0];
            int normalRow = sparseArrs[i][1];
            int normalVal = sparseArrs[i][2];
            normalArrs[normalCol][normalRow]=normalVal;
        }
        return normalArrs;
    }



    public void print(int[][] arrs){
        for(int[] arr:arrs){
            for(int i:arr){
                System.out.printf("%d\t",i);
            }
            System.out.println();
        }
    }
}
